// 重构字符串 时间复杂度 O(N + M),N为s的长度,M为t的长度; 空间复杂度 O(1)

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        build(s);
        build(t);
        return s == t;
    }
    void build(string& s) {
        auto it = s.begin();
        while (it != s.end()) {
            if (*it == '#') {
                s.erase(it);
                if (it - 1 >= s.begin()) {
                    s.erase(it - 1);
                    it--;
                }
            }
            else {
                it++;
            }
        }
    }
};